package com.liuwei.spring.cloud.junit.leetcode.hots;

import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

@Slf4j
public class NumberOfProvinces {

    public static void main(String[] args) {
        int[][]isConnected = new int[][]{{1,1,0},{1,1,0},{0,0,1}};
        NumberOfProvinces solution = new NumberOfProvinces();
        int number = solution.findCircleNum(isConnected);
        log.info("number:{}",number);
    }

    public int findCircleNum(int[][] isConnected) {
        // 构造树形结构
        List<Province> provinces = new ArrayList<>();
        for (int i = 0; i < isConnected.length; i++) {
            int[] row = isConnected[i];
            Province province = new Province();
            province.setProvince(i);
            for (int j = 0; j < row.length; j++) {
                int connected = row[j];
                if(connected==1){
                    province.addConnected(j);
                }
            }
            province.getConnected().remove(String.valueOf(i));
            provinces.add(province);
        }

        // 遍历属性结构
        Map<String,Province> map = provinces.stream().collect(Collectors.toMap(x->String.valueOf(x.getProvince()), Function.identity()));
        Set<String> done = new HashSet<>();
        int total = 0;
        for (int i = 0; i < provinces.size(); i++) {
            String provinceValue = String.valueOf(i);
            if(done.contains(provinceValue)){
                continue;
            }
            find(map,map.get(String.valueOf(i)),done);
            total ++;
        }
        return total;
    }

    public void find(Map<String,Province> map,Province province,Set<String> done){
        String value = String.valueOf(province.getProvince());
        done.add(value);
        Set<String> connected = province.connected;
        if(done.containsAll(connected)){
            return;
        }
        Iterator<String> it = connected.iterator();
        while(it.hasNext()){
            String relatedValue = it.next();
            Province relatedProvince = map.get(relatedValue);
            if(!done.contains(relatedValue)){
                find(map,relatedProvince,done);
            }
        }

    }


    public static class Province{
        private int province;
        private Set<String> connected = new HashSet<>();

        public int getProvince() {
            return province;
        }

        public void setProvince(int province) {
            this.province = province;
        }

        public Set<String> getConnected() {
            return connected;
        }

        public void setConnected(Set<String> connected) {
            this.connected = connected;
        }

        public void addConnected(int i){
            connected.add(String.valueOf(i));
        }
    }
}
